package bst;

import java.util.ArrayList;
import java.util.List;
import bst.BST;
import bst.BSTNode;
import bt.BTNode;

/**
 * Projeto : Arvore Preta e Vermelha
 * 
 * Equipe:
 * 			Antonio Eduardo
 * 			Gabriel de Brito
 * 			Gervasio Costa
 * 			Jordan Ferreira
 * 			Wesley Breno
 * 
 */

public class BSTImpl<V extends Comparable<V>> implements BST<V> {

	protected final BTNode<V> NIL = new BSTNode<V>();
	protected BSTNode<V> root;

	public BSTImpl() {
		root = new BSTNode<V>();
	}

	public BSTNode<V> getRoot() {
		return this.root;
	}

	@Override
	public boolean isEmpty() {
		return root.isEmpty();
	}

	@Override
	public int height() {
		return height(root);
	}

	protected int height(BSTNode<V> node) {
		int leftHeight = 0, rigthHeight = 0;

		if (node.isEmpty())
			return -1;

		if (!node.getLeft().isEmpty())
			leftHeight += 1 + height((BSTNode<V>) node.getLeft());
		if (!node.getRight().isEmpty())
			rigthHeight += 1 + height((BSTNode<V>) node.getRight());

		return Math.max(leftHeight, rigthHeight);
	}

	@Override
	public BTNode<V> search(V element) {
		return search(element, root);
	}

	protected BTNode<V> search(V element, BTNode<V> node) {
		BTNode<V> result = node;
		if (!node.isEmpty()) {
			if (element.compareTo(node.getData()) == 0)
				result = node;
			else if (element.compareTo(node.getData()) < 0)
				result = search(element, node.getLeft());
			else
				result = search(element, node.getRight());
		}
		return result;
	}

	@Override
	public void insert(V element) {
		BSTNode<V> aux = root;
		if (element != null) {
			while (search(element).isEmpty()) {
				if (aux.isEmpty()) {
					aux.setData(element);
					aux.setLeft(new BSTNode<V>());
					aux.setRight(new BSTNode<V>());
					aux.getLeft().setParent(aux);
					aux.getRight().setParent(aux);
				} else if (element.compareTo(aux.getData()) > 0) {
					aux = (BSTNode<V>) aux.getRight();
				} else {
					aux = (BSTNode<V>) aux.getLeft();
				}
			}
		}
	}

	@Override
	public BSTNode<V> maximum() {
		return maximum(root);
	}

	private BSTNode<V> maximum(BSTNode<V> node) {
		if (node.isEmpty())
			return null;
		if (node.getRight().isEmpty())
			return node;
		return maximum((BSTNode<V>) node.getRight());
	}

	@Override
	public BSTNode<V> minimum() {
		return minimum(root);
	}

	private BSTNode<V> minimum(BSTNode<V> node) {
		if (node.isEmpty())
			return null;
		if (node.getLeft().isEmpty())
			return node;
		return minimum((BSTNode<V>) node.getLeft());
	}

	@Override
	public BSTNode<V> sucessor(BSTNode<V> node) {

		BSTNode<V> nodeAux;
		BSTNode<V> retorno1;
		BSTNode<V> retorno2;

		nodeAux = (BSTNode<V>) search(node.getData());

		if (nodeAux.isEmpty())
			return null;
		else
			retorno1 = minimum((BSTNode<V>) nodeAux.getRight());
		if (retorno1 == null) {
			retorno2 = procuraSucesorPeloParent(nodeAux, nodeAux.getParent());
		} else {
			return retorno1;
		}

		if (nodeAux.getData().compareTo(retorno2.getData()) < 0)
			return retorno2;
		return retorno1;

	}

	private BSTNode<V> procuraSucesorPeloParent(BSTNode<V> node,
			BTNode<V> parentAtual) {
		if (parentAtual == null)
			return node;
		else {
			if (node.getData().compareTo(parentAtual.getData()) < 0)
				return (BSTNode<V>) parentAtual;
			else {
				return procuraSucesorPeloParent(node, parentAtual.getParent());
			}
		}
	}

	@Override
	public BSTNode<V> predecessor(BSTNode<V> node) {

		BSTNode<V> nodeAux;
		BSTNode<V> retorno1;
		BSTNode<V> retorno2;

		nodeAux = (BSTNode<V>) search(node.getData());

		if (nodeAux.isEmpty())
			return null;
		else
			retorno1 = maximum((BSTNode<V>) nodeAux.getLeft());
		if (retorno1 == null) {
			retorno2 = procuraPredecessorPeloParent(nodeAux,
					nodeAux.getParent());
		} else {
			return retorno1;
		}

		if (nodeAux.getData().compareTo(retorno2.getData()) > 0)
			return retorno2;
		return retorno1;
	}

	private BSTNode<V> procuraPredecessorPeloParent(BSTNode<V> node,
			BTNode<V> parentAtual) {

		if (parentAtual == null)
			return node;
		else {
			if (node.getData().compareTo(parentAtual.getData()) > 0) {
				return (BSTNode<V>) parentAtual;
			} else {
				return procuraPredecessorPeloParent(node,
						parentAtual.getParent());
			}
		}
	}

	@Override
	public void remove(V element) {
		BSTNode<V> node = (BSTNode<V>) this.search(element);
		if (node.isEmpty()) {
			return;
		}
		if (!node.isEmpty()) {
			if (node.getLeft().isEmpty() && node.getRight().isEmpty()) {
				node.setData(null);
				node.setLeft(new BSTNode<V>());
				node.setRight(new BSTNode<V>());
			} else {
				if (node.getLeft().isEmpty() && !node.getRight().isEmpty()
						|| node.getRight().isEmpty()
						&& !node.getLeft().isEmpty()) {
					if (node.getParent() != null) {
						if (node.getData()
								.compareTo(node.getParent().getData()) < 0) {
							if (!node.getLeft().isEmpty()) {
								node.getParent().setLeft(node.getLeft());
							} else {
								node.getParent().setLeft(node.getRight());
							}
						} else {
							if (!node.getLeft().isEmpty()) {
								node.getParent().setRight(node.getLeft());
							} else {
								node.getParent().setRight(node.getRight());
							}
						}
					} else {
						if (!node.getRight().isEmpty()) {
							root = (BSTNode<V>) node.getRight();
						} else {
							root = (BSTNode<V>) node.getLeft();
						}
						node = null;
						root.setParent(node);
					}
				} else {
					V sucessor = sucessor(node).getData();
					remove(sucessor);
					node.setData(sucessor);

				}
			}
		}
	}

	@Override
	public V[] preOrder() {
		@SuppressWarnings("unchecked")
		V[] retorno = (V[]) new Comparable[size()];
		List<V> retornoPreOrder = new ArrayList<V>();
		retornoPreOrder = preOrder(retornoPreOrder, root);
		for (int i = 0; i < retorno.length; i++) {
			retorno[i] = retornoPreOrder.get(i);
		}
		return retorno;
	}

	private List<V> preOrder(List<V> list, BTNode<V> node) {
		if (node.isEmpty())
			return list;
		else {
			list.add(node.getData());
			preOrder(list, node.getLeft());
			preOrder(list, node.getRight());
		}
		return list;
	}

	@Override
	public V[] order() {
		@SuppressWarnings("unchecked")
		V[] retorno = (V[]) new Comparable[size()];
		List<V> retornoOrder = new ArrayList<V>();
		retornoOrder = order(retornoOrder, root);
		for (int i = 0; i < retorno.length; i++) {
			retorno[i] = retornoOrder.get(i);
		}
		return retorno;
	}

	private List<V> order(List<V> list, BTNode<V> node) {
		if (node.isEmpty())
			return list;
		else {
			order(list, node.getLeft());
			list.add(node.getData());
			order(list, node.getRight());
		}
		return list;
	}

	@Override
	public V[] postOrder() {
		@SuppressWarnings("unchecked")
		V[] retorno = (V[]) new Comparable[size()];
		List<V> retornaPostOrder = new ArrayList<V>();
		retornaPostOrder = postOrder(retornaPostOrder, root);
		for (int i = 0; i < retorno.length; i++) {
			retorno[i] = retornaPostOrder.get(i);
		}
		return retorno;
	}

	private List<V> postOrder(List<V> list, BTNode<V> node) {
		if (node.isEmpty())
			return list;
		else {
			postOrder(list, node.getLeft());
			postOrder(list, node.getRight());
			list.add(node.getData());
		}
		return list;
	}

	@Override
	public int size() {
		return size(root);
	}

	private int size(BTNode<V> node) {
		int result = 0;
		if (!node.isEmpty())
			result = 1 + size(node.getLeft()) + size(node.getRight());
		return result;
	}

	public boolean isSimilar(BSTImpl<V> arvore) {
		return isSimilar(root, arvore.getRoot());
	}

	private boolean isSimilar(BSTNode<V> node1, BSTNode<V> node2) {
		if (node1.isEmpty() && node2.isEmpty()) {
			return true;
		} else if ((node1.isEmpty() != node2.isEmpty())) {
			return false;
		} else {
			return isSimilar((BSTNode<V>) node1.getLeft(),
					(BSTNode<V>) node2.getLeft())
					&& isSimilar((BSTNode<V>) node1.getRight(),
							(BSTNode<V>) node2.getRight());
		}
	}

	public int leafNumber() {
		return leafNumber(root);
	}

	private int leafNumber(BSTNode<V> node) {
		if (node.isEmpty()) {
			return 0;
		} else if (node.isLeaf()) {
			return 1;
		} else {
			return leafNumber((BSTNode<V>) node.getLeft())
					+ leafNumber((BSTNode<V>) node.getRight());
		}
	}

	public boolean equals(BSTImpl<V> tree) {
		if (isSimilar(tree)) {
			return auxEquals((BTNode<V>) root, (BTNode<V>) tree.getRoot());
		} else {
			return false;
		}
	}

	private boolean auxEquals(BTNode<V> node1, BTNode<V> node2) {
		if (node1.isEmpty() && node2.isEmpty()) {
			return true;
		} else if (!node1.getData().equals(node2.getData())) {
			return false;
		} else {
			return auxEquals((BTNode<V>) node1.getLeft(),
					(BTNode<V>) node2.getLeft())
					&& auxEquals((BTNode<V>) node1.getRight(),
							(BTNode<V>) node2.getRight());
		}
	}

}